package main.Q301_400;

import java.util.*;

public class Q381_390 {
    public static void main(String[] args) {
        System.out.println("Question381：");
        System.out.println("Question382：链表随机节点");
        System.out.println("Question383：赎金信");
        System.out.println("Question384：打乱数组");
        System.out.println("Question385：");
        System.out.println("Question386：字典序排数");
        System.out.println(Question386.lexicalOrder(13));
        System.out.println("Question387：字符串中的第一个唯一字符");
        System.out.println("Question388：");
        System.out.println("Question389：找不同");
        System.out.println("Question390：消除游戏");
    }
}

class Question382{
    int size;
    ListNode head;
    public Question382(ListNode head) {
        this.head=head;
        int count=0;
        while (head!=null){
            count++;
            head=head.next;
        }
        this.size=count;
    }

    public int getRandom() {
        int index=new Random().nextInt(this.size)+1;
        ListNode cur=new ListNode();
        cur.next=this.head;
        for (int i=0;i<index;i++) cur=cur.next;
        return cur.val;
    }
}

class Question383{
    public static boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

class Question384{
    int[] nums;
    int[] original;

    public Question384(int[] nums) {
        this.nums = nums;
        this.original = new int[nums.length];
        System.arraycopy(nums, 0, original, 0, nums.length);
    }

    public int[] reset() {
        System.arraycopy(original, 0, nums, 0, nums.length);
        return nums;
    }

    public int[] shuffle() {
        int[] shuffled = new int[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; ++i) {
            list.add(nums[i]);
        }
        Random random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            int j = random.nextInt(list.size());
            shuffled[i] = list.remove(j);
        }
        System.arraycopy(shuffled, 0, nums, 0, nums.length);
        return nums;
    }
}

class Question386{
    public static List<Integer> lexicalOrder(int n) {
        List<Integer> list=new ArrayList<>();
        TreeSet<Integer> set=new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                char[] str1=String.valueOf(o1).toCharArray();
                char[] str2=String.valueOf(o2).toCharArray();
                int i=0,j=0;
                while (i< str1.length&&j< str2.length){
                    if (str1[i]<str2[j]) return -1;
                    else if (str1[i]>str2[j]) return 1;
                    else {
                        i++;
                        j++;
                    }
                }
                if (i== str1.length&&j!= str2.length) return -1;
                else return 1;
            }
        });
        for (int i=1;i<=n;i++) set.add(i);
        list.addAll(set);
        return list;
    }
}

class Question387{
    public static int firstUniqChar(String s) {
        int[] charCount=new int[123];
        for (char c:s.toCharArray()) charCount[c]++;
        int index=Integer.MAX_VALUE;
        for (int i=0;i<charCount.length;i++){
            if (charCount[i]==1&&s.indexOf(i)<index){
                index=s.indexOf(i);
            }
        }
        if (index==Integer.MAX_VALUE) index=-1;
        return index;
    }
}

class Question389{
    public static char findTheDifference(String s, String t) {
        int[] counts=new int[26];
        char result=' ';
        for (char c:s.toCharArray()) counts[c-'a']++;
        for (char c:t.toCharArray()) counts[c-'a']--;
        for (int i=0;i< counts.length;i++)
            if (counts[i]<0) {
                result= (char) (i+'a');
                break;
            }
        return result;
    }
}

class Question390{
    public int lastRemaining(int n) {
        int result=0;
        if (n==1) return 1;
        else if (n>=2&&n<=5) return 2;
        else if (n==6||n==7) return 4;
        else {//自8开始循环，4个为一组
            int a=n/8;
            int b=n-8*a;
            int c=b%4;
            if (c==0||c==1) result=6;
            else result=8;
        }
        return result;
    }
}